/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
class Solution {
  public:
//     vector<TreeLinkNode*> nodes;
//     TreeLinkNode* GetNext(TreeLinkNode* pNode) {
//         TreeLinkNode* root = pNode;
//         // 获取根节点
//         while (root->next) root = root->next;

//         // 中序遍历用nodes储存所有节点指针
//         InOrder(root);
//         int n = nodes.size();

//         for (int i = 0; i < n - 1; i++) {
//             TreeLinkNode* cur = nodes[i];
//             // 将结点进行匹配
//             if (pNode == cur) {
//                 // 如果有匹配到给出的结点，则下一个结点即返回结果
//                 return nodes[i + 1];
//             }
//         }
//         // 否则如果没有下一个结点则返回NULL
//         return NULL;
//     }
//     // 中序遍历
//     void InOrder(TreeLinkNode* root) {
//         if (root == NULL) return;
//         InOrder(root->left);
//         nodes.push_back(root);
//         InOrder(root->right);
//     }
    
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        // 如果有右子树
        if (pNode->right) {
            TreeLinkNode* rchild = pNode->right;
            // 一直找到右子树的最左下的结点为返回值
            while (rchild->left) rchild = rchild->left;
            return rchild;
        }
        // 如果无右子树且当前结点是其父节点的左子结点
        if (pNode->next && pNode->next->left == pNode) {
            // 返回当前结点的父节点
            return pNode->next;
        }
        // 如果无右子树且当前结点是其父节点的右子节点
        if (pNode->next) {
            TreeLinkNode* ppar = pNode->next;
            // 沿着左上一直爬树，爬到当前结点是其父节点的左自己结点为止
            while (ppar->next && ppar->next->right == ppar) ppar = ppar->next;
            // 返回当前结点的父节点
            return ppar->next;
        }
        return NULL;
    }
    };